package com.mocchira.dq2011.sp;

import java.util.ArrayList;
import java.util.Collections;
import java.util.EmptyStackException;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
//import java.util.Random;
import java.util.Stack;

import com.mocchira.dq2011.sp.SlidePuzzleAnalyzer.Result.Direction;
import com.mocchira.dq2011.sp.SlidePuzzleInputParser.Puzzle;

public class SlidePuzzleAnalyzer {
    public static class Result {
        public static enum Direction {
            L,
            R,
            U,
            D
        }
        private int lc = 0, rc = 0, uc = 0, dc = 0;
        private List<Direction> directions = new ArrayList<Direction>();
        public String toString() {
            StringBuilder dst = new StringBuilder();
            for (Direction dir: directions) {
                dst.append(dir.name());
            }
            return dst.toString();
        }
        public void add(Direction dir) {
            directions.add(dir);
            if (dir.equals(Direction.L)) {
                lc++;
            } else if (dir.equals(Direction.R)) {
                rc++;
            } else if (dir.equals(Direction.U)) {
                uc++;
            } else if (dir.equals(Direction.D)) {
                dc++;
            }
        }
        private void add(char c) {
            String sdir = String.valueOf(c);
            Direction dir = null;
            if (sdir.equals(Direction.L.name())) {
                dir = Direction.L;
            } else if (sdir.equals(Direction.R.name())) {
                dir = Direction.R;
            } else if (sdir.equals(Direction.U.name())) {
                dir = Direction.U;
            } else if (sdir.equals(Direction.D.name())) {
                dir = Direction.D;
            }
            add(dir);
        }
        public void addFromAnswerString(String answer) {
            for (int i = 0; i < answer.length(); i++) {
                add(answer.charAt(i));
            }
        }
        public int getLNum() {
            return lc;
        }
        public int getRNum() {
            return rc;
        }
        public int getUNum() {
            return uc;
        }
        public int getDNum() {
            return dc;
        }
    }
    
    private class RollbackInfo {
        public Result.Direction dir;
        List<Integer> fixedRowList = new ArrayList<Integer>();
        List<Integer> fixedColList = new ArrayList<Integer>();
        int[] pos = {-1, -1};//pos[0]=x;pos[1]=y
    }
    
    private class DeadlineException extends Exception {
        
        private static final long serialVersionUID = 1L;

        public DeadlineException(String msg) {
            super(msg);
        }

    }
    
    private Stack<RollbackInfo> stack;
    private Result result = null;
    private SlidePuzzleInputParser.Puzzle puzzle;
    private char[][] v2dimension; // placed walls around the all boards
    private char[][] fixedBrock;
    private int fixedW;
    private int fixedH;
    private int fixedLeft;
    private int fixedTop;
    private char[] tmp1dim;
    private int curX;
    private int curY;
    private Direction rollbackDir = null;
    private HistoryManager history;
    private RouteManager route = new RouteManager();
    
    private List<Direction> initialDirections;
    public volatile boolean reqStop = false;
    
    private static final int TIMEOUT_INC_UNIT = 210 * 1000;
    private int maxDepth;
    private long timeout = 120 * 1000;
    private long starttime = 0;
    
    private static final int DEPTH_INC_UNIT = 20;
    private int incDepthNum = 0;
    
    private static final char FIXED = '1';
    private static final char NONE  = '0';
    private static final int  FIXED_MIN_SIZE = 3;
    
    private class HistoryManager {
        private int idx = 0;
        private List<Set<Direction>> historyList;
        public HistoryManager(int maxDepath) {
            historyList = new ArrayList<Set<Direction>>(maxDepath+2);
            for (int i = 0; i < maxDepath+2; i++) {
                historyList.add(new HashSet<Direction>(4));
            }
        }
        public void setIndex(int i) {
            idx = i;
            historyList.set(idx + 1, new HashSet<Direction>(4));
        }
        public boolean checkHistory(Direction dir) {
            Set<Direction> now = historyList.get(idx);
            return now.contains(dir); 
        }
        public void addHistory() {
            Set<Direction> now = historyList.get(idx);
            now.add(stack.peek().dir);
        }
    }
    
    private interface IRoute {
        boolean canGo();
        void go();
    }
    
    private class RouteManager {
        private class Left implements IRoute {
            @Override
            public boolean canGo() {
                return canLeft();
            }
            @Override
            public void go() {
                left(false);
            }
            
        }
        private class Right implements IRoute {
            @Override
            public boolean canGo() {
                return canRight();
            }
            @Override
            public void go() {
                right(false);
            }
            
        }
        private class Up implements IRoute {
            @Override
            public boolean canGo() {
                return canUp();
            }
            @Override
            public void go() {
                up(false);
            }
            
        }
        private class Down implements IRoute {
            @Override
            public boolean canGo() {
                return canDown();
            }
            @Override
            public void go() {
                down(false);
            }
            
        }
        @SuppressWarnings("serial")
        List<IRoute> routes = new ArrayList<SlidePuzzleAnalyzer.IRoute>(4){{add(new Left());add(new Right());add(new Up());add(new Down());}};
        public boolean go() {
            Collections.shuffle(routes);
            for (IRoute route: routes) {
                if (route.canGo()) {
                    route.go();
                    return true;
                }
            }
            return false;
        }
    }
    
    public SlidePuzzleAnalyzer(SlidePuzzleInputParser.Puzzle puzzle, List<Direction> iniDirs, Result result, int timeout) {
        this.result = result;
        this.initialDirections = iniDirs;
        this.puzzle = puzzle;
        this.timeout = timeout * 1000;
        stack = new Stack<RollbackInfo>();
        tmp1dim = new char[puzzle.boards.length];
        v2dimension = new char [puzzle.height + 2][];
        fixedBrock = new char [puzzle.height + 2][];
        for (int y = 0; y < v2dimension.length; y++) {
            v2dimension[y] = new char[puzzle.width + 2];
            fixedBrock[y] = new char[puzzle.width + 2];
            for (int x = 0; x < v2dimension[y].length; x++) {
                if (y == 0 || (y == (v2dimension.length - 1))) {
                    // top && bottom
                    v2dimension[y][x] = SlidePuzzleInputParser.Puzzle.WALL;
                    fixedBrock[y][x]  = FIXED;
                } else {
                    if (x == 0 || (x == (v2dimension[y].length - 1))) {
                        // lef && right
                        v2dimension[y][x] = SlidePuzzleInputParser.Puzzle.WALL;
                        fixedBrock[y][x]  = FIXED;
                    } else {
                        v2dimension[y][x] = puzzle.boards[dim2index(x, y)];
                        if (v2dimension[y][x] == SlidePuzzleInputParser.Puzzle.BLANK) {
                            curX = x;
                            curY = y;
                        }
                        fixedBrock[y][x]  = NONE;
                    }
                }
            }
        }
        fixedW = puzzle.width;
        fixedH = puzzle.height;
        fixedLeft = 1;
        fixedTop  = 1;
    }
    
    private int getUnfixedRowNum() {
        final char[] rb = puzzle.getResultBoards();
        int c = 0;
        for (int x = fixedLeft; x < fixedLeft + fixedW; x++) {
            int idx = dim2index(x, fixedTop);
            if (v2dimension[fixedTop][x] != rb[idx])
                c++;
        }
        return c;
    }
    
    private int getUnfixedColNum() {
        final char[] rb = puzzle.getResultBoards();
        int c = 0;
        for (int y = fixedTop; y < fixedTop + fixedH; y++) {
            int idx = dim2index(fixedLeft, y);
            if (v2dimension[y][fixedLeft] != rb[idx])
                c++;
        }
        return c;
    }
    
    private boolean isPossibleRoute() {
        if (fixedW == FIXED_MIN_SIZE && fixedH == FIXED_MIN_SIZE) {
            return true;
        }
        int need = getUnfixedColNum() + getUnfixedRowNum();
        int remain = maxDepth - stack.size();
        return (remain - need) > 0;
    }
    
    private boolean casFixedRow(int y) {
        final char[] rb = puzzle.getResultBoards();
        for (int x = fixedLeft; x < fixedLeft + fixedW; x++) {
            int idx = dim2index(x, y);
            if (v2dimension[y][x] != rb[idx])
                return false;
        }
        int cnum = 0;
        for (int x = fixedLeft; x < fixedLeft + fixedW; x++) {
            int idx = dim2index(x, y+1);
            if (v2dimension[y+1][x] != Puzzle.WALL && v2dimension[y+1][x] != rb[idx]) {
                cnum++;
            } else {
                if (cnum == 1) {
                    return false;
                }
                cnum = 0;
            }
        }
        if (cnum == 1)
            return false;
        for (int x = fixedLeft; x < fixedLeft + fixedW; x++) {
            fixedBrock[y][x] = FIXED;
        }
        return true;
    }
    
    private boolean casFixedCol(int x) {
        final char[] rb = puzzle.getResultBoards();
        for (int y = fixedTop; y < fixedTop + fixedH; y++) {
            int idx = dim2index(x, y);
            if (v2dimension[y][x] != rb[idx])
                return false;
        }
        int cnum = 0;
        for (int y = fixedTop; y < fixedTop + fixedH; y++) {
            int idx = dim2index(x+1, y);
            if (v2dimension[y][x+1] != Puzzle.WALL && v2dimension[y][x+1] != rb[idx]) {
                cnum++;
            } else {
                if (cnum == 1) {
                    return false;
                }
                cnum = 0;
            }
        }
        if (cnum == 1)
            return false;
        for (int y = fixedTop; y < fixedTop + fixedH; y++) {
            fixedBrock[y][x] = FIXED;
        }
        return true;
    }
    
    private void casFixedPos(int[] pos) {
        final char[] rb = puzzle.getResultBoards();

        int rest = fixedH - FIXED_MIN_SIZE;
        // check left-top
        int restX = fixedW - 2;
        if (rest > 0) {
            int i = 0;
            for (; i < restX; i++) {
                int x = fixedLeft+i;
                int idx = dim2index(x, fixedTop);
                if (v2dimension[fixedTop][x] == rb[idx] && 
                    v2dimension[fixedTop][x+2] != Puzzle.WALL && 
                    v2dimension[fixedTop+1][x+2] != Puzzle.WALL &&
                    v2dimension[fixedTop+1][x+1] != Puzzle.WALL && 
                    v2dimension[fixedTop+2][x+1] != Puzzle.WALL &&
                    v2dimension[fixedTop+2][x] != Puzzle.WALL) {
                    if (fixedBrock[fixedTop][x] != FIXED) {
                        fixedBrock[fixedTop][x] = FIXED;
                        pos[0] = x;
                        pos[1] = fixedTop;
                        return;
                    }
                } else {
                    break;
                }
            }
            restX -= i;
            // check right-top
            if (restX > 0) {
                for (i = 0; i < restX; i++) {
                    int x = fixedLeft+fixedW-1-i;
                    int idx = dim2index(x, fixedTop);
                    if (v2dimension[fixedTop][x] == rb[idx] && 
                        v2dimension[fixedTop][x-2] != Puzzle.WALL && 
                        v2dimension[fixedTop+1][x-2] != Puzzle.WALL &&
                        v2dimension[fixedTop+1][x-1] != Puzzle.WALL && 
                        v2dimension[fixedTop+2][x-1] != Puzzle.WALL &&
                        v2dimension[fixedTop+2][x] != Puzzle.WALL) {
                        if (fixedBrock[fixedTop][x] != FIXED) {
                            fixedBrock[fixedTop][x] = FIXED;
                            pos[0] = x;
                            pos[1] = fixedTop;
                            return;
                        }
                    } else {
                        break;
                    }
                }
            }
        }
        
        // check left-top
        rest = fixedW - FIXED_MIN_SIZE;
        int restY = fixedH - 2;
        if (rest > 0) {
            int i = 0;
            for (; i < restY; i++) {
                int y = fixedTop+i;
                int idx = dim2index(fixedLeft, y);
                if (v2dimension[y][fixedLeft] == rb[idx] && 
                    v2dimension[y][fixedLeft+2] != Puzzle.WALL && 
                    v2dimension[y+1][fixedLeft+2] != Puzzle.WALL &&
                    v2dimension[y+1][fixedLeft+1] != Puzzle.WALL && 
                    v2dimension[y+2][fixedLeft+1] != Puzzle.WALL &&
                    v2dimension[y+2][fixedLeft] != Puzzle.WALL) {
                    if (fixedBrock[y][fixedLeft] != FIXED) {
                        fixedBrock[y][fixedLeft] = FIXED;
                        pos[0] = fixedLeft;
                        pos[1] = y;
                        return;
                    }
                } else {
                    break;
                }
            }
            restY -= i;
            // check left-bottom
            if (restY > 0) {
                for (i = 0; i < restY; i++) {
                    int y = fixedTop+fixedH-1-i;
                    int idx = dim2index(fixedLeft, y);
                    if (v2dimension[y][fixedLeft] == rb[idx] && 
                        v2dimension[y][fixedLeft+2] != Puzzle.WALL && 
                        v2dimension[y-1][fixedLeft+2] != Puzzle.WALL &&
                        v2dimension[y-1][fixedLeft+1] != Puzzle.WALL && 
                        v2dimension[y-2][fixedLeft+1] != Puzzle.WALL &&
                        v2dimension[y-2][fixedLeft] != Puzzle.WALL) {
                        if (fixedBrock[y][fixedLeft] != FIXED) {
                            fixedBrock[y][fixedLeft] = FIXED;
                            pos[0] = fixedLeft;
                            pos[1] = y;
                            return;
                        }
                    } else {
                        break;
                    }
                }
            }
        }
        
    }
    
    private void initFixedPos() {
        final char[] rb = puzzle.getResultBoards();

        int rest = fixedH - FIXED_MIN_SIZE;
        // check left-top
        int restX = fixedW - 2;
        if (rest > 0) {
            int i = 0;
            for (; i < restX; i++) {
                int x = fixedLeft+i;
                int idx = dim2index(x, fixedTop);
                if (v2dimension[fixedTop][x] == rb[idx] && 
                    v2dimension[fixedTop][x+2] != Puzzle.WALL && 
                    v2dimension[fixedTop+1][x+2] != Puzzle.WALL &&
                    v2dimension[fixedTop+1][x+1] != Puzzle.WALL &&
                    v2dimension[fixedTop+2][x+1] != Puzzle.WALL &&
                    v2dimension[fixedTop+2][x] != Puzzle.WALL) {
                    fixedBrock[fixedTop][x] = FIXED;
                } else {
                    break;
                }
            }
            restX -= i;
            // check right-top
            if (restX > 0) {
                for (i = 0; i < restX; i++) {
                    int x = fixedLeft+fixedW-1-i;
                    int idx = dim2index(x, fixedTop);
                    if (v2dimension[fixedTop][x] == rb[idx] && 
                        v2dimension[fixedTop][x-2] != Puzzle.WALL && 
                        v2dimension[fixedTop+1][x-2] != Puzzle.WALL &&
                        v2dimension[fixedTop+1][x-1] != Puzzle.WALL &&
                        v2dimension[fixedTop+2][x-1] != Puzzle.WALL &&
                        v2dimension[fixedTop+2][x] != Puzzle.WALL) {
                        fixedBrock[fixedTop][x] = FIXED;
                    } else {
                        break;
                    }
                }
            }
        }
        
        // check left-top
        rest = fixedW - FIXED_MIN_SIZE;
        int restY = fixedH - 2;
        if (rest > 0) {
            int i = 0;
            for (; i < restY; i++) {
                int y = fixedTop+i;
                int idx = dim2index(fixedLeft, y);
                if (v2dimension[y][fixedLeft] == rb[idx] && 
                    v2dimension[y][fixedLeft+2] != Puzzle.WALL && 
                    v2dimension[y+1][fixedLeft+2] != Puzzle.WALL &&
                    v2dimension[y+1][fixedLeft+1] != Puzzle.WALL && 
                    v2dimension[y+2][fixedLeft+1] != Puzzle.WALL &&
                    v2dimension[y+2][fixedLeft] != Puzzle.WALL) {
                    fixedBrock[y][fixedLeft] = FIXED;
                } else {
                    break;
                }
            }
            restY -= i;
            // check left-bottom
            if (restY > 0) {
                for (i = 0; i < restY; i++) {
                    int y = fixedTop+fixedH-1-i;
                    int idx = dim2index(fixedLeft, y);
                    if (v2dimension[y][fixedLeft] == rb[idx] && 
                        v2dimension[y][fixedLeft+2] != Puzzle.WALL && 
                        v2dimension[y-1][fixedLeft+2] != Puzzle.WALL &&
                        v2dimension[y-1][fixedLeft+1] != Puzzle.WALL && 
                        v2dimension[y-2][fixedLeft+1] != Puzzle.WALL &&
                        v2dimension[y-2][fixedLeft] != Puzzle.WALL) {
                        fixedBrock[y][fixedLeft] = FIXED;
                    } else {
                        break;
                    }
                }
            }
        }
        
    }
    
    private void rollbackFixedRow(int y) {
        fixedTop--;
        fixedH++;
        for (int x = fixedLeft; x < fixedLeft + fixedW; x++) {
            fixedBrock[y][x] = NONE;
        }
    }
    
    private void rollbackFixedCol(int x) {
        fixedLeft--;
        fixedW++;
        for (int y = fixedTop; y < fixedTop + fixedH; y++) {
            fixedBrock[y][x] = NONE;
        }
    }
    
    private void rollbackFixedPos(int x, int y) {
        fixedBrock[y][x] = NONE;
    }
    
    private void doFixed(List<Integer> fixedRows, List<Integer> fixedCols) {
        if (fixedW == FIXED_MIN_SIZE && fixedH == FIXED_MIN_SIZE) {
            // nothing to do
            return;
        }
        if (fixedH > FIXED_MIN_SIZE) {
            // try to shlink starting from top.
            int rest = fixedH - FIXED_MIN_SIZE;
            while (rest > 0 && casFixedRow(fixedTop)) {
                fixedRows.add(fixedTop);
                fixedTop++;
                fixedH--;
                rest--;
                int inc = DEPTH_INC_UNIT - (incDepthNum * 3);
                maxDepth += inc;
                incDepthNum++;
                if (timeout > 0)
                    timeout += TIMEOUT_INC_UNIT;
            }
        }
        if (fixedW > FIXED_MIN_SIZE) {
            // try to shlink starting from left.
            int rest = fixedW - FIXED_MIN_SIZE;
            if (fixedH > FIXED_MIN_SIZE)
                rest++;
            while (rest > 0 && casFixedCol(fixedLeft)) {
                fixedCols.add(fixedLeft);
                fixedLeft++;
                fixedW--;
                rest--;
                int inc = DEPTH_INC_UNIT - (incDepthNum * 3);
                maxDepth += inc;
                incDepthNum++;
                if (timeout > 0)
                    timeout += TIMEOUT_INC_UNIT;
            }
        }
    }
    
    public String toString() {
        StringBuilder dst = new StringBuilder("---virtual 2dimention---" + System.getProperty("line.separator"));
        for (int y = 0; y < v2dimension.length; y++) {
            dst.append(v2dimension[y]);
            dst.append(System.getProperty("line.separator"));
        }
        return dst.toString();
    }
    
    private void calcMaxDepth(int inc) {
        int areaSize = puzzle.height * puzzle.width /* - puzzle.numWall */;
        maxDepth = (int)(areaSize * 1.5);
        maxDepth += inc;
        maxDepth = 50;
    }
    
    private int dim2index(int x, int y) {
        // sub around walls
        x -= 1;
        y -= 1;
        int ret = y * puzzle.width + x;
        return ret;
    }
    
    private boolean canUp() {
        try {
            if (fixedBrock[curY-1][curX] == FIXED)
                return false;
            if (rollbackDir != null && rollbackDir.equals(Direction.U))
                return false;
            if (history.checkHistory(Direction.U))
                return false;
            Direction dir = stack.peek().dir;
            return v2dimension[curY-1][curX] != SlidePuzzleInputParser.Puzzle.WALL && !dir.equals(Direction.D);
        } catch (EmptyStackException ex) {
            return v2dimension[curY-1][curX] != SlidePuzzleInputParser.Puzzle.WALL;
        }
    }
    private boolean canDown() {
        try {
            if (fixedBrock[curY+1][curX] == FIXED)
                return false;
            if (rollbackDir != null && rollbackDir.equals(Direction.D))
                return false;
            if (history.checkHistory(Direction.D))
                return false;
            Direction dir = stack.peek().dir;
            return v2dimension[curY+1][curX] != SlidePuzzleInputParser.Puzzle.WALL && !dir.equals(Direction.U);
        } catch (EmptyStackException ex) {
            return v2dimension[curY+1][curX] != SlidePuzzleInputParser.Puzzle.WALL;
        }
    }
    private boolean canLeft() {
        try {
            if (fixedBrock[curY][curX-1] == FIXED)
                return false;
            if (rollbackDir != null && rollbackDir.equals(Direction.L))
                return false;
            if (history.checkHistory(Direction.L))
                return false;
            Direction dir = stack.peek().dir;
            return v2dimension[curY][curX-1] != SlidePuzzleInputParser.Puzzle.WALL && !dir.equals(Direction.R);
        } catch (EmptyStackException ex) {
            return v2dimension[curY][curX-1] != SlidePuzzleInputParser.Puzzle.WALL;
        }
    }
    private boolean canRight() {
        try {
            if (fixedBrock[curY][curX+1] == FIXED)
                return false;
            if (rollbackDir != null && rollbackDir.equals(Direction.R))
                return false;
            if (history.checkHistory(Direction.R))
                return false;
            Direction dir = stack.peek().dir;
            return v2dimension[curY][curX+1] != SlidePuzzleInputParser.Puzzle.WALL && !dir.equals(Direction.L);
        } catch (EmptyStackException ex) {
            return v2dimension[curY][curX+1] != SlidePuzzleInputParser.Puzzle.WALL;
        }
    }
    
    private void up(boolean rollback) {
        char tmp = v2dimension[curY-1][curX];
        v2dimension[curY-1][curX] = v2dimension[curY][curX];
        v2dimension[curY][curX] = tmp;
        curY--;
        if (!rollback) {
            RollbackInfo ri = new RollbackInfo();
            ri.dir = Direction.U;
            casFixedPos(ri.pos);
            doFixed(ri.fixedRowList, ri.fixedColList);
            stack.push(ri);
            rollbackDir = null;
        }
    }
    private void down(boolean rollback) {
        char tmp = v2dimension[curY+1][curX];
        v2dimension[curY+1][curX] = v2dimension[curY][curX];
        v2dimension[curY][curX] = tmp;
        curY++;
        if (!rollback) {
            RollbackInfo ri = new RollbackInfo();
            ri.dir = Direction.D;
            casFixedPos(ri.pos);
            doFixed(ri.fixedRowList, ri.fixedColList);
            stack.push(ri);
            rollbackDir = null;
        }
    }
    private void left(boolean rollback) {
        char tmp = v2dimension[curY][curX-1];
        v2dimension[curY][curX-1] = v2dimension[curY][curX];
        v2dimension[curY][curX] = tmp;
        curX--;
        if (!rollback) {
            RollbackInfo ri = new RollbackInfo();
            ri.dir = Direction.L;
            casFixedPos(ri.pos);
            doFixed(ri.fixedRowList, ri.fixedColList);
            stack.push(ri);
            rollbackDir = null;
        }
    }
    private void right(boolean rollback) {
        char tmp = v2dimension[curY][curX+1];
        v2dimension[curY][curX+1] = v2dimension[curY][curX];
        v2dimension[curY][curX] = tmp;
        curX++;
        if (!rollback) {
            RollbackInfo ri = new RollbackInfo();
            ri.dir = Direction.R;
            casFixedPos(ri.pos);
            doFixed(ri.fixedRowList, ri.fixedColList);
            stack.push(ri);
            rollbackDir = null;
        }
    }
    
    private void genTmp1dim() {
        for (int y = 1; y < v2dimension.length - 1; y++) {
            char[] src = v2dimension[y];
            System.arraycopy(src, 1, tmp1dim, (y - 1) * puzzle.width, puzzle.width);
        }
    }
    
    private boolean isGoal() {
        if ((curY == (v2dimension.length - 2)) && (curX == (v2dimension[0].length - 2))) {
            genTmp1dim();
            return puzzle.matchResultPos(tmp1dim);
        } else {
            return false;
        }
    }
    
    private void rollback() {
        try {
            RollbackInfo ri = stack.pop();
            rollbackDir = ri.dir;
            if (rollbackDir.equals(Direction.U)) {
                down(true);
            } else if (rollbackDir.equals(Direction.D)) {
                up(true);
            } else if (rollbackDir.equals(Direction.L)) {
                right(true);
            } else if (rollbackDir.equals(Direction.R)) {
                left(true);
            }
            if (ri.pos[0]!=-1 && ri.pos[1] != -1) {
                rollbackFixedPos(ri.pos[0], ri.pos[1]);
            }
            for (Integer x: ri.fixedColList) {
                rollbackFixedCol(x);
                incDepthNum--;
                int inc = DEPTH_INC_UNIT - (incDepthNum * 3);
                maxDepth -= inc;
                if (timeout > 0)
                    timeout -= TIMEOUT_INC_UNIT;
            }
            for (Integer y: ri.fixedRowList) {
                rollbackFixedRow(y);
                incDepthNum--;
                int inc = DEPTH_INC_UNIT - (incDepthNum * 3);
                maxDepth -= inc;
                if (timeout > 0)
                    timeout -= TIMEOUT_INC_UNIT;
            }
        } catch (EmptyStackException ex) {
            ;
        }
    }

    private int nest = 0;
    
    private int search() throws DeadlineException {
        if (timeout > 0) {
            long now = System.currentTimeMillis();
            if ((now - starttime) > timeout) {
                String msg = "maxDepth:" + maxDepth + " timeout:" + timeout;
                throw new DeadlineException(msg);
            }
        }
        if (reqStop) {
            String msg = "maxDepth:" + maxDepth + " timeout:" + timeout;
            throw new DeadlineException(msg);
        }
        nest++;
        history.setIndex(nest-1);
        try {
            if (isGoal()) {
                return -1;
            } else {
                int ret = 0;
                while (ret != -1) {
                    //System.out.print(this);
                    if (!isPossibleRoute()) {
                        rollback();
                        return 0;
                    }
                    if (!route.go()) {
                        rollback();
                        return 0;
                    }
                    history.addHistory();
                    if (stack.size() > maxDepth) {
                        rollback();
                        continue;
                    }
                    ret = search();
                }
                return -1;
            }
        } finally {
            nest--;
            history.setIndex(nest-1);
        }
    }
    
    /*
    private void swap(char[] src, int srcPos, int dstPos) {
        char tmp = src[dstPos];
        src[dstPos] = src[srcPos];
        src[srcPos] = tmp;
    }
    */
    
    // eliminate routes if goes through the start position.
    private void genResult() {
        // init
        /*
        int cpos = 0;
        int startPos = 0;
        System.arraycopy(puzzle.boards, 0, tmp1dim, 0, puzzle.boards.length);
        for (int i = 0; i < tmp1dim.length; i++) {
            if (tmp1dim[i] == SlidePuzzleInputParser.Puzzle.BLANK) {
                cpos = i;
                break;
            }
        }
        for (int i = 0; i < stack.size(); i++) {
            Direction dir = stack.get(i).dir;
            if (dir.equals(Direction.D)) {
                swap(tmp1dim, cpos, cpos + puzzle.width);
                cpos += puzzle.width;
            } else if (dir.equals(Direction.U)) {
                swap(tmp1dim, cpos, cpos - puzzle.width);
                cpos -= puzzle.width;
            } else if (dir.equals(Direction.R)) {
                swap(tmp1dim, cpos, cpos + 1);
                cpos += 1;
            } else if (dir.equals(Direction.L)) {
                swap(tmp1dim, cpos, cpos - 1);
                cpos -= 1;
            }
            // check
            if (puzzle.matchStartPos(tmp1dim)) {
                startPos = i;
                break;
            }
        }
        */
        // generates Result Object
        for (Direction dir: initialDirections) {
            result.add(dir);
        }
        for (int i = 0; i < stack.size(); i++) {
            Direction dir = stack.get(i).dir;
            result.add(dir);
        }
    }
    
    public Result execute() {
        calcMaxDepth(0);
        history = new HistoryManager(200);
        // initialized fixed boards
        initFixedPos();
        doFixed(new ArrayList<Integer>(), new ArrayList<Integer>());
        // initialized boards by specified directions
        Direction pre = null;
        for (Direction dir: initialDirections) {
            if (dir.equals(Direction.U)) {
                if (canUp() && (pre == null || pre != null && !pre.equals(Direction.D))) {
                    up(true);
                } else {
                    return result;
                }
            } else if (dir.equals(Direction.D)) {
                if (canDown() && (pre == null || pre != null && !pre.equals(Direction.U))) {
                    down(true);
                } else {
                    return result;
                }
            } else if (dir.equals(Direction.L)) {
                if (canLeft() && (pre == null || pre != null && !pre.equals(Direction.R))) {
                    left(true);
                } else {
                    return result;
                }
            } else if (dir.equals(Direction.R)) {
                if (canRight() && (pre == null || pre != null && !pre.equals(Direction.L))) {
                    right(true);
                } else {
                    return result;
                }
            }
            pre = dir;
        }
        starttime = System.currentTimeMillis();
        try {
            if (search() == -1) {
                genResult();
            }
        } catch (DeadlineException de) {
            System.out.println(de.getMessage());
        }
        return result;
    }
}
